class Solution1 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(combinationSum4(arr , 4));
    }
    public static int combinationSum4(int[] nums, int target) {
         int len = nums.length ;
         int[] dp = new int[target+1] ;
         dp[0] =1 ;
         for(int i=0 ; i<= target ; i ++){
            for(int j = 0 ; j< len ; j ++){
                if(i >= nums[j]){
                    dp[i] += dp[i-nums[j]] ;
                }  
            }
         }
        return dp[target] ; 
    }
}